﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Problem3
{
    /*This program finds the greatest prime factor of a number*/
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Input number greater than 2 \n");
            long input = long.Parse(Console.ReadLine());
            while (input < 2)
            {
                Console.Write("Number must be greater than 2 \n");
                input = long.Parse(Console.ReadLine());
            }
            long output = gpf(input);
            Console.Write("Greates prime factor of "+input.ToString() + " is: " + output.ToString() + "\n");
            Console.Write("Press anykey to exit");
            Console.ReadLine();
        }

        static long gpf(long n)
        {
            long size = (long)Math.Floor(Math.Sqrt(n));
            bool[] sieve = new bool[size];
            for (long i = 0; i < size; i++)
            {
                sieve[i] = true;
            }
            long max = 1;
            for (long i = 2; i < size; i++)
            {
                if (sieve[i]==true && n % i == 0)
                {
                    n = n / i;
                    max = i;
                    for (long j = i; j < size; j += i)
                        sieve[j] = false;
                }
            }
            return max;
        }
    }
}
